home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7217 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.1 KB  |  45 lines
  1. Newsgroups: comp.lang.c
  2. Path: undergrad.math.uwaterloo.ca!clgonsal
  3. From: clgonsal@undergrad.math.uwaterloo.ca (Carl Laurence Gonsalves)
  4. Subject: Re: Huffman Coding
  5. Sender: news@undergrad.math.uwaterloo.ca (news spool owner)
  6. Message-ID: <DMuBJ6.92t@undergrad.math.uwaterloo.ca>
  7. Date: Thu, 15 Feb 1996 23:21:05 GMT
  8. References: <4fvtbt$ils@garuda.csulb.edu>
  9. Nntp-Posting-Host: cayley.uwaterloo.ca
  10. Organization: University of Waterloo
  11.  
  12. In article <4fvtbt$ils@garuda.csulb.edu>, Jose Reyes <joreyes@csulb.edu> wrote:
  13. >Does anyone have any good algorithms for Huffman encoding and decoding?  
  14. >If so could you either post them to the group or send them to me.  Thanks.
  15.  
  16. Pretty well any book on algorithms will have the basic Huffman
  17. encoding/decoding algorithm which shouldn't be too hard to turn into code.
  18.  
  19. Encoding consists of generating your table, and then outputiing the correct
  20. code for each thing in your input stream. The hard part is generating the
  21. table, which is actually pretty easy. You start of with a node for each
  22. character in your alphabet. Each node also has a "weight" which is the
  23. frequency or probability of that character.
  24.  
  25. Push all your nodes into a priority queue. Extract the two minimum nodes
  26. and create a new node as their parent. Push that node into the priority
  27. queue. Repeat n-1 times (where n is the number of leaf-nodes). You now have
  28. a huffman tree.
  29.  
  30. From the tree you can generate an encoding table. Each "code" will have one
  31. bit for each edge along the path from the root to the leaf. use something
  32. like 0 for left, 1 for right. 
  33.  
  34. To decode you need to recreate the tree (how you do that is up to you...
  35. you need to transmit either the frequency data, the table, or some other
  36. encoding of the tree), and then you just take one step down the tree for
  37. each bit you read in. When you hit a leaf output the code and jump back to
  38. the root.
  39.  
  40. -- 
  41.         Carl Laurence Gonsalves - clgonsal@undergrad.math.uwaterloo.ca
  42.                    Computer Science, University of Waterloo
  43.                http://www.undergrad.math.uwaterloo.ca/~clgonsal/
  44.                    http://www.csclub.uwaterloo.ca/~clgonsal/
  45.